package leetcode.editor.cn;

import java.util.*;

public class P406QueueReconstructionByHeight {
    public static void main(String[] args) {
        Solution solution = new P406QueueReconstructionByHeight().new Solution();
        solution.reconstructQueue(new int[][]{{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people, (o1, o2) -> {
                int i = o1[1] - o2[1];
                return i == 0 ? o1[0] - o2[0] : i;
            });
            List<int[]> result = new ArrayList<>();

            for (int[] person : people) {
                int high = person[0], num = person[1];
                int size = result.size();
                int count = 0;
                int index = 0;
                boolean find = false;
                for (; index < size; index++) {
                    int[] pre = result.get(index);
                    if (pre[0] >=high) {
                        count++;
                    }
                    if (count == num) {
                        if (result.size() > index + 1 && result.get(index + 1)[0] > high) {
                            result.add(index + 1, person);
                            find = true;
                            break;
                        }
                    }
                }
                if (!find) {
                    result.add(person);
                }
            }
            for (int i = 0; i < result.size(); i++) {
                people[i] = result.get(i);
            }
            return people;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}